
"""
NC65 斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=117&&tqId=37760&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#


class Solution:

    memo = {}

    def method1(self, n: int) -> int:
        """
        递归调用+记忆化搜索
        """

        if n <= 2:
            return 1

        if n not in self.memo:
            res = self.method1(n-1) + self.method1(n-2)
            self.memo[n] = res

        return self.memo[n]

    def method2(self, n: int) -> int:
        """
        递推法
        时间复杂度：O(n)
        空间复杂度：O(n)
        """

        lst = [0]*(n+1)  # 把0也考虑在内
        lst[1] = 1

        for i in range(2, n+1):
            lst[i] = lst[i-1] + lst[i-2]

        return lst[n]

    def method3(self, n: int) -> int:
        """
        题目要求，空间复杂度为O(1)
        我们改一下method2，不要存那么多数据
        我们其实只要保留前面2个数据就好
        """

        f1 = f2 = 1  # 斐波那契数，前2个数都为1

        for i in range(3, n+1):
            f1, f2 = f2, f1+f2

        return f2

    def Fibonacci(self, n: int) -> int:
        # write code here
        assert n >= 0, "n can not be a negative number."

        if n <= 2:
            return 1

        return self.method3(n)


def test():
    obj = Solution()
    res = obj.Fibonacci(4)
    print(res)


if __name__ == "__main__":
    test()
